#pragma once

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <string>
#include <sys/types.h>
#include <sys/stat.h>
#include <process.h>
#include <io.h>
#include <windows.h>

typedef struct _Freqperchar {
	unsigned char c;
	size_t cnt;
	double p;
	double P;
} Freqperchar;

typedef struct _TreeNode {
	size_t cnt;
	Freqperchar* leaf;
	struct _TreeNode* left;
	struct _TreeNode* right;
} TreeNode;

typedef struct _ListNode {
	size_t cnt;
	struct _TreeNode* tree;
	struct _ListNode* next;
} ListNode;

typedef struct _BitStream {
	unsigned char* base;
	unsigned char* ptr;
	unsigned char offset;
	size_t capacity;
} BitStream;

void bsshift1(BitStream* bs)
{
	/* shift the offset of bitstream bs */
	bs->offset++;
	if (bs->offset % (sizeof(unsigned char) * 8) == 0) {
		bs->ptr++;
		bs->offset = 0;
	}
}

void bswriteb(BitStream* bs, unsigned char b)
{
	/* write the least significant bit of b into the bitstrem bs (LSB) */
	*(bs->ptr) &= ((unsigned char)0xff >> (8 - bs->offset));
	if (b & 1)
		* (bs->ptr) |= (1 << bs->offset);
	bsshift1(bs);
}

unsigned char bsgetb(BitStream* bs)
{
	/* get the LSB of the bitstream bs */
	unsigned char bit = (*(bs->ptr) & (1 << bs->offset)) >> bs->offset;
	bsshift1(bs);
	return bit;
}

BitStream* bsnew(unsigned char* buffer, size_t cap)
{
	BitStream* bs = (BitStream*)malloc(sizeof(BitStream));
	if (!bs) exit(-1);	// malloc error
	bs->base = buffer;
	bs->ptr = buffer;
	bs->capacity = cap;
	bs->offset = 0;
	return bs;
}

int sortbycnt(const void* a, const void* b)
{
	return ((Freqperchar*)b)->cnt - ((Freqperchar*)a)->cnt;
}

int sortbyc(const void* a, const void* b)
{
	return (*(Freqperchar * *)a)->c - (*(Freqperchar * *)b)->c;
}

void assigncode(const TreeNode* tree, size_t level)
{
	Freqperchar* freqleaf = tree->leaf;
	if (freqleaf) {
		// if (freqleaf->c == 0x4d || freqleaf->c == 0x6a)
		//     printf("%02x: p = %.20lf\n", freqleaf->c, pow(0.5, level));
		freqleaf->p = pow(0.5, level);
		return;
	}
	// printf("go left\n");
	assigncode(tree->left, level + 1);
	// printf("go up and right\n");
	assigncode(tree->right, level + 1);
}
